/*
* @(#) KMP.java 2018年02月23日
*
* Copyright 2010 NetEase.com, Inc. All rights reserved.
*/
package com.leo.m1802.d23;

import java.util.logging.Level;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月23日
 */
public class KMP {
//    private static int[] getnext(String s){
//        int[] next = new int[s.length()];
//        next[0] = 0;
//        int i = 1;
//        int j = 0;
//        while (i < s.length()){
//            if (s.charAt(i) == s.charAt(j)){
//                i++;
//                j++;
//                next[i]=j;
//            }else {
//                j = next[j];
//            }
//        }
//        return next;
//    }
//    public static int isMathch(String s, String p){
//        int[] next = getnext(s);
//        int i = 0;
//        int j = 0;
//        while (i<s.length() && j<p.length()){
//            if (s.charAt(i) == p.charAt(j)){
//                i++;
//            }else {
//                i = next[i];
//            }
//            j++;
//        }
//
//        if (i == s.length()){
//            return j-i;
//        }
//        return -1;
//    }

    /**
     * 基本匹配算法
     * @param s 主字符串
     * @param p 匹配的字符串
     * @return
     */
    public static int bp(String s, String p){
        int i=0,j=0;
        while (i<s.length() && j<p.length()){
            if (s.charAt(i) == p.charAt(j)){
                i++;
                j++;
            }else {
                i = i-j+1;
                j = 0;
            }
        }

        if (j == p.length()){
            return i-j;
        }
        return -1;
    }

    /**
     * kmp匹配
     * @param s 主字符串
     * @param p 需要匹配的字符串
     * @return
     */
    public static int isMathch(String s, String p){
        int[] next = getnext(p);
        int i=0,j=0;
        while (i<s.length() && j<p.length()){
            if (j==-1 || s.charAt(i) == p.charAt(j)){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }

        if (j == p.length()){
            return i-j;
        }
        return -1;
    }
    private static int[] getnext(String s){
        int[] next = new int[s.length()];
        int i = 0;
        int j = -1;
        next[0] = -1;
        while (i<s.length()){
            if (j==-1 || s.charAt(i)==s.charAt(j)){
                i++;
                j++;
                next[i]=j;
            }else {
                j = next[j];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(bp("BBC ABCDAB ABCDABCDABDE","ABCDABD"));
    }
}
